In high speed packet transmission networks, routing of packets through the network is accomplished by means of routing information in the packet header. Such a network is composed of nodes interconnected by transmission links. Nodes include packet switching mechanisms for selectively launching received packets on outgoing transmission links. Some of these nodes are called end nodes and provide user access to the network. When analyzed as a graph, such networks can be characterized as a graph of switches, user stations, and the edges connecting them together. Edges connecting switches together correspond to the transmission links interconnecting such switching mechanisms. Edges connecting user stations (user applications) to the network at end nodes are called terminal edges. Adapter circuits at each of the switching mechanisms adapt the packet signals for transmission on or delivery to the transmission links and user applications, respectively. Many different types of packet switching mechanisms and transmission links can be accommodated in such packet transmission systems.
Routing information for such networks can be expressed in many different forms, two major modes of which are called Automatic Network Routing (ANR), used to deliver a packet to a single destination user station, and Tree Multicast Mode (TMM), used to deliver the same packet to a plurality of destination user stations. In ANR routing, the successive links in the route are specified, in routing order, by transmission link labels in the routing field. Along the route, as the packet is switched to a new link, that link label is stripped away from the routing field to leave the next-to-be-used link label as the first label in the routing field. Automatic Network Routing is described in "PARIS: An Approach to Integrated High-Speed Networks" by I. Cidon and I. S. Gopal, International Journal of Digital and Analog Cabled Systems, Vol. 1, No. 2, April-June, 1988, pages 77-85.
In TMM routing, multicast trees are predefined to connect a desired subset of user stations connected to the packet transmission network. In this connection, a "tree" is defined as a connected set of switches, packet user stations, and edges having no cycles or loops. The term "multicast" is defined as a single sender transmitting packets to a multiplicity of receiving user stations. The multicast tree is identified in the routing field by a tree address. Rather than stripping the tree address from the routing field, this address is used at each switching point in the tree to route the packet to all other connected switches or user stations of the same tree (except the switch or user station from which the packet was received). In this way, any user station of a multicast tree can launch a packet with the tree address in the routing field and have that packet delivered to all of the other user stations of the same multicast tree. Such multicast tree routing is described in "Distributed Control for PARIS," by B. Awerbuch, I. Cidon, I. Gopal, M. Kaplan and S. Kutten, Proceedings of the 9 th ACM Symposium on Principles of Distributed Computing, Quebec, Canada, August, 1990, pages 145-159.
Due to the differing protocols for processing the routing field to provide ANR and TMM routing, it has heretofore been impossible to mix these two types of routing in the same packet header. It is often desirable, however, to deliver a packet to all of the user stations of a multicast tree from an originating user station which is not itself a member of the multicast tree. For example, a plurality of adapters may be connected to a particular Local Area Network (LAN). One such local LAN adapter may wish to send a request to a remote group of LAN adapters which are associated with a second LAN and connected by a multicast tree for information about the stations of than second LAN. Similarly, an end node may wish to simultaneously send a query to a group of directory service providers which have been, for update convenience, connected by a multicast tree. A significant problem, then, is to allow such remote access to multicast trees.